Non-volatile (NV) memories, such as electrically erasable programmable read only memories (EEPROMs) or NOR and NAND Flash memories typically have limited write cycles before failing, and may exhibit adjacent bit failures after too many read cycles. In NV memory, reads tend to be more robust than writes, so most uses of these memories have been in read-intensive modes such as streaming audio and video, but recent developments have seen an increasing use of Flash Memories in Solid State Disks (SSDs), which require a higher frequency of writes and much higher data integrity. As such, there are numerous patents, such as U.S. Pat. No. 6,601,211 by Norman, granted Jul. 29, 2003, and U.S. Pat. No. 8,010,876 by Hsieh et al., granted Aug. 30, 2011, which describe including Error Correction Codes (ECC) in each page of memory to detect and correct flash read errors. In addition, Keeler suggests a two-dimensional application of ECC to blocks of data storage in U.S. Pat. No. 6,910,174, granted Jun. 21, 2005. The present inventor has been granted a number of patents, including U.S. Pat. No. 7,412,636, granted Aug. 12, 2008, U.S. Pat. No. 7,421,563 granted Sep. 2, 2008, and their continuations, all of which may be applicable to serial ECC generation and error correction.
Still, block erasures and page or word writes, where blocks may be much larger than the pages or words, may fail after a number of cycles. To extend this limited life, numerous patents, such as U.S. Pat. No. 6,732,221 by Ban, granted May 4, 2004, and U.S. Pat. No. 8,001,318 by Iyer et al., granted Aug. 16, 2011, describe techniques called wear leveling. Wear leveling may be used to reduce the maximum number of write cycles to any specific block of memory by writing to unused memory before erasing and reusing previously used memory.
As the non-volatile memory wears out, the errors increase. Individual pages may fail on write or read cycles, and whole blocks may fail on erasure. These failures may constitute an accumulation of individual bit failures after any given operation. As the number of these bit failures increase, ECC may no longer correct them. In some systems these pages or blocks may be marked bad and removed from the available storage. In such systems, the memory capacity appears to reduce as the NV memory begins to wear out. Some NV memory systems begin with failures, which may be marked as bad blocks or pages before being used.
FIG. 1 is a high-level diagram of a typical system for managing these forms of error correction. The system may include NV memory 10 and a microprocessor 14 that performs the ECC generation and error correction, and which translates the incoming control and logical addresses 15 from the host into physical addresses for accessing the NV memory 10, as required for the wear leveling process. The microprocessor keeps the address translation tables and copies of the lists of bad pages and blocks in the volatile Random Access Memory (RAM) 11.
Non-volatile memories, such as phase-change memories or flash memories, are typically slower than volatile memory such as Static RAM (SRAM) or Dynamic RAM (DRAM). In order to improve the read-write performance of the NV memory 10, the RAM 11 is employed to temporarily hold the recently accessed data, for transmission either to the NV memory 12 or to the external host 13.
One patent, U.S. Pat. No. 5,479,638 by Assar et al. granted Dec. 26, 1995, suggests applying traditional CAMs to a wear leveling technique to reduce the read latency. The inventor has previously patented a serial CAM structure in U.S. Pat. No. 7,369,422 granted May 6, 2008, which has the advantage of using a regular two-port memory.
Such techniques have resulted in a multi-chip solution, which tracks the use of NV memory, not the actual errors due to its use. It is known that these errors increase gradually, and eventually make the blocks and pages unusable, and it is also known that while errors increase with use, they may otherwise be very random. And yet none of the current methods measure the actual errors or attempt to continue to use defective storage, beyond simple error correction.